from typing import List


class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        # o(n)
        i, j, ln = 0, 0, len(nums)
        m, ans = nums[i], 0
        while i < ln and j < ln:
            if m >= s:
                if ans == 0 or j - i + 1 < ans:
                    ans = j - i + 1
                m -= nums[i]
                i += 1
            else:
                j += 1
                if j < ln:
                    m += nums[j]
        # o(nlogn)
        i, ln, ans = 0, len(nums), 0
        sums = [0, ]
        for i in range(1, ln):
            sums.append(sums[i - 1] + nums[i - 1])
        i = 0
        while i < ln:
            l, r = i, ln - 1
            while r > l:
                h = (r + l) // 2
                m = sums[h] - sums[i] + nums[h]
                if m == s:
                    r = h
                    break
                elif m > s:
                    r = h
                else:
                    l = h + 1
            m = sums[r] - sums[i] + nums[r]
            if m >= s:
                if ans == 0 or r - i + 1 < ans:
                    ans = r - i + 1
            i += 1
        return ans


solve = Solution()
s0, nums0 = 7, [2, 3, 1, 2, 4, 3]
questions = [
    (7, [2, 3, 1, 2, 4, 3]),
    (213, [12, 28, 83, 4, 25, 26, 25, 2, 25, 25, 25, 12])
]
for qi, q in enumerate(questions, 1):
    print(f'#{qi}:', q)
    print('ans:', solve.minSubArrayLen(q[0], q[1]))


